// 给定一个单链表的头节点的head,要求将链表中的奇数位置上的节点排在前面，偶数位置上的节点排在后面，返回新的链表节点
// 要求空间复杂度为O(1)

// 思路：遍历链表，用cur指向当前节点，odd指向当前奇数节点，even指向当前偶数节点，遍历完后更新拼接到一起
// 时间复杂度：O(n)
// 空间复杂度：O(1)

const { LinkedList, ListNode} = require('./64.设计链表')

function oddEvenList(head) {
    if (!head || !head.next || !head.next.next) {
        return head
    }
    let odd = head
    let even = head.next
    let evenHead = head.next
    let cur = head.next.next
    let isOdd = true
    while (cur) {
        if (isOdd) {
            odd.next = cur
            odd = cur
        } else {
            even.next = cur
            even = cur
        }
        cur = cur.next
        isOdd = !isOdd
    }
    odd.next = evenHead
    even.next = null
    return head
}

let head = [1, 2, 3, 4, 5]
let node = new LinkedList(head)
console.log(oddEvenList(node.head))